/*
 * @Author: szx
 * @Date: 2022-03-18 13:17:04
 * @LastEditTime: 2022-03-18 13:31:45
 * @Description:
 * @FilePath: \leetcode\剑指offer\12\12.js
 */
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    const m = board.length;
    const n = board[0].length;
    const flag = new Array(m).fill(false).map(() => new Array(n).fill(false));
    const dfs = (i, j, index) => {
        if (index == word.length) return true;
        if (i < 0 || i >= m || j < 0 || j >= n || flag[i][j]) return false;
        if (word[index] == board[i][j]) {
            flag[i][j] = true;
            if (dfs(i + 1, j, index + 1)) return true;
            if (dfs(i, j + 1, index + 1)) return true;
            if (dfs(i - 1, j, index + 1)) return true;
            if (dfs(i, j - 1, index + 1)) return true;
            flag[i][j] = false;
        }
        return false;
    };
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] == word[0]) {
                if (dfs(i, j, 0)) return true;
            }
        }
    }
    return false;
};
